package newcoder_exp.justPractise;
import java.util.*;
import org.junit.*;
import tree.*;
public class NC6 {
    public class Solution {
        //最大路径和
        public int maxPathSum (TreeNode root) {
            return maxPath(root).max;
        }

        public Info maxPath(TreeNode root) {
            if (root == null) {
                return new Info(Integer.MIN_VALUE, Integer.MIN_VALUE);
            }
            Info left = maxPath(root.left),
            right = maxPath(root.right);

            //sum获得的应该是以当前节点为路径节点的一条单线路径值(且为最大的一条)
            int sum = root.val; //若三者都为负数，也能得到为负输出的情况
            int bigger = Math.max(left.sum, right.sum);
            if (bigger > 0) sum += bigger;
            
            int other = bigger == left.sum ? right.sum : left.sum;
            //max描绘的是当前的最大值，已经成型不可改变的路径，因此左右若sum都是正值都可以考虑上，再加上当前val
            int max = Math.max(left.max, right.max);
            int sumMax = root.val;
            if (bigger > 0) {
                sumMax += bigger;
            } 
            if (other > 0) {
                sumMax += other;
            }
            max = Math.max(sumMax, max);
            return new Info(max, sum);
        }

        public class Info {
            public int max;
            public int sum;

            public Info(int max, int sum) {
                this.max = max;
                this.sum = sum;
            }
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        TreeNode root = TreeUtils.deserialization("{-519,-283,-42,322,103,#,263,826,-706,920,691,-38,-765,#,#,-658,386,328,-214,-159,284,281,#,122,-920,59,#,-838,#,588,-167,824,723,-502,-17,-898,492,#,-373,884,777,603,-44,#,-723,-678,#,-426,536,683,#,-368,-845,-762,-218,-997,757,-992,685,-519,-990,#,-959,64,#,878,435,-640,#,#,481,-139,#,#,#,#,#,#,-273,433,-256,-47,#,-588,-547,764,681,#,-894,122,-162,521,-237,#,-132,-567,-148,199,-653,982,-752,-420,#,-535,877,#,-15,729,-294,#,#,#,#,#,#,#,#,#,#,350,-85,656,47,#,#,33,#,#,-219,#,#,822,#,-817,-944,-184,213,652,#,-11,#,529,389,-895,#,#,#,-933,#,484,-817,555,735,-232,#,-233,-566,196,285,-538,#,879,225,#,-213,#,#,#,#,#,#,-321,-887,#,#,685,-76,#,#,#,853,76,#,-512,-526,#,490,#,#,-318,-386,#,#,#,-400,#,#,934,604,#,#,#,#,149,-523,962,-501,-624,-743,-134,731,-468,-83,585,484,579,765,#,-125,480,#,#,836,#,#,#,#,#,#,-237,#,#,#,-833,-218,#,#,#,609,#,#,-129,#,#,928,#,-69,#,#,#,#,#,-189,#,#,#,#,#,-739,-388,#,#,#,-670,-550,#,-483,#,#,#,-850,#,#,#,#,#,#,#,#,-10,#,#,995,#,#,#,#,#,#,#,#,#,-388,880,#,-251,-988,#,#,#,#,615,-897,#,#,#,#,#,#,#,#,#,#,680,#,177,#,#,#,-485,#,-34,81,#,#,#,#,375,-371,#,699,#,#,#,-788,#,#,#,#,-847,490,-571,#,-151,#,#,-597,#,854,#,#,-715,#,#,#,#,#,#,#,#,#,#,#,#,#,-731,-845,384,201,#,#,#,#,#,-682,#,927}");
        int res = s.maxPathSum(root);
        System.out.println(res);
    }
}

/* 

{
"生成 vue 模板": {
"prefix": "vue",
"body": [
"<template>",
"<div></div>",
"</template>","",
"<script>",
"//这里可以导入其他文件（比如： 组件， 工具 js， 第三方插件 js， json
文件， 图片文件等等） ",
"//例如： import 《组件名称》 from '《组件路径》 ';",
"",
"export default {",
"//import 引入的组件需要注入到对象中才能使用",
"components: {},",
"props: {},",
"data() {",
"//这里存放数据",
"return {",
"",
"};",
"},",
"//计算属性 类似于 data 概念",
"computed: {},",
"//监控 data 中的数据变化",
"watch: {},",
"//方法集合",
"methods: {",
"",
"},",
"//生命周期 - 创建完成（可以访问当前 this 实例） ",
"created() {",
"",
"},",
"//生命周期 - 挂载完成（可以访问 DOM 元素） ",
"mounted() {",
"",
"},",
"beforeCreate() {}, //生命周期 - 创建之前",
"beforeMount() {}, //生命周期 - 挂载之前",
"beforeUpdate() {}, //生命周期 - 更新之前",
"updated() {}, //生命周期 - 更新之后",
"beforeDestroy() {}, //生命周期 - 销毁之前",
"destroyed() {}, //生命周期 - 销毁完成",
"activated() {}, //如果页面有 keep-alive 缓存功能， 这个函数会触发
",
"}",
"</script>",
"<style lang='scss' scoped>",
"//@import url($3); 引入公共 css 类","$4",
"</style>"
],
"description": "生成 vue 模板"
}
}





*/
